<?php
/**
 * User: helloJiu
 * Date: 2021/9/27
 * Time: 10:08
 */

namespace App\Algorithm\DP;


class LengthOfCommonSubSequence
{
    /**
     * https://leetcode-cn.com/problems/maximum-length-of-repeated-subarray/
     * @param $nums1
     * @param $nums2
     * @return int|mixed
     */
    function findLength($nums1, $nums2) {
        // $dp[$i][$j] 表示 在$i-1 和 $j-1 结尾的最大子序列长度
        $dp = [];
        if (empty($nums1) || empty($nums2)) {
            return 0;
        }

        $len_1 = count($nums1);
        $len_2 = count($nums2);

        for ($i = 0; $i <= $len_1; $i++) {
            $dp[$i][0] = 0;
        }

        for ($j = 0; $j <= $len_2; $j++) {
            $dp[0][$j] = 0;
        }

        $max_len = 0;

        for ($i = 1; $i <= $len_1; $i++) {
            for ($j = 1; $j <= $len_2; $j++) {
                if ($nums1[$i-1] == $nums2[$j-1]){
                    $dp[$i][$j] = $dp[$i-1][$j-1] + 1;
                    if($max_len < $dp[$i][$j]) $max_len = $dp[$i][$j];
                }else{
                    // 不相等时, 直接置0
                    $dp[$i][$j] = 0;
                }
            }
        }

        return $max_len;
    }
}